High performance packet switches that interconnect a plurality of input ports to a plurality of output ports are critical components in communication networks requiring high transmission speeds. These switches can be used to transfer packets carrying a variety of services such as video, image, voice, and data services. Because of the high transfer rates, these switches are typically implemented using highly distributed, self-routing interconnection networks. In order to ease hardware implementation, these switches usually operate in a time-slotted fashion where the time slot is equal to the transmission time of one packet.
Packet switches traditionally incorporate buffers in order to deal with temporary surges in traffic. The placement of buffers in a packet switch strongly influences the packet loss, packet delay, and throughput performance. Packet switches having buffers at the switch input ("input buffered switches") and that transfer packets on a First-In-First-Out (FIFO) basis suffer from head-of-line blocking which results in reduced throughput performance (see J. Y. Hui and E. Arthurs, ``A broadband packet switch for integrated transport,`` IEEE J. Select. Areas in Commun., vol. SAC-5, pp. 1264-1273, Dec. 1987). On the other hand, packet switches having buffers at the switch output ("output buffered switches") can achieve maximum throughput close to 100% (see Y. S. Yeh, M. G. Hluchyj and A. S. Acampora, ``The Knockout switch: A simple, modular architecture for high-performance packet switching,`` IEEE J. Select. Areas Commun., vol. SAC-5, pp. 734-743, Oct. 1987). Since an output buffer must be able to accept simultaneous packet arrivals (up to the number of input lines for no packet loss), the switch interconnection fabric normally provides multiple, and up to N.sup.2, disjoint paths from its N inputs to its N outputs. As a result, a straightforward implementation of an output-buffered switch can lead to hardware complexity of up to N.sup.2 in the case where a hardware unit is dedicated to each path.
In addition to the placement of buffers, buffer allocation is also an important consideration in packet switch design. When buffers are dedicated to packets destined to each output of a switch, a large buffer size is required to attain a low packet loss rate. At the other extreme, when buffers are completely shared by all the outputs, significant buffer reductions can be achieved under certain traffic conditions. Examples of shared-buffer switches with a centralized control can be found in the Prelude and Hitachi proposals (see M. Devault, J. Cochennec, and M. Servel, ``The Prelude ATD experiment: assessments and future prospects,`` IEEE J. Select. Areas in Commun., vol. SAC-6, pp. 1528-1537, Dec. 1988 and H. Kuwuhara, N. Endo, M. Ogino, and T. Kozaki, ``Shared buffer memory switch for an ATM exchange,`` Proc. ICC, Boston, Mass., pp. 4.4.1-4.1.5, June, 1989). An example of a packet switch with distributed control is the Starlite switch (see A. Huang and S. Knauer, ``Starlite: A Wideband Digital Switch,`` Proc. GLOBECOM'84, Atlanta, Ga., pp. 121-125, Dec. 1984, and U.S. Pat. Nos. 4,516,238 and 4,542,497 (Huang et al)). Since a shared storage buffer can be accessed by any input and any output, some inputs that coincidentally send packets to a specific group of outputs can consume all of the buffer space, thereby preventing (or ``locking out``) other packets destined for other outputs to access the buffer space. This phenomenon in turn degrades the performance of the switch. In view of the lock-out problem, it is thus more desirable to allocate only a partial amount-of the buffer space as a shared storage and dedicate parts of the remaining buffer space to each output.
A variety of packet switches based on the combination of Batcher sorting and banyan routing networks have been proposed. One example is the Starlite switch discussed above, which is based on the Batcher sorting network, a trap network, and a banyan routing network. The Batcher network sorts the incoming packets according to the destination addresses (See K. Batcher, ``Sorting Networks and their Applications,`` Proc. AFIPS, pp. 307-314, 1968). The trap network identifies packets with repeated addresses and recirculates them to the input of the Batcher network. The packets that are not recirculated by the trap network are routed to the output ports in nonblocking fashion by a banyan network. Unfortunately, to achieve high performance, the size of the Batcher network needs to be a large multiple of the input lines. This increases the hardware complexity. The Starlite switch also suffers from the buffer lock-out problem discussed above because of its full buffer sharing configuration. The Sunshine switch disclosed in J. Giacopelli, M. Littlewood, and W. D. Sincoskie, ``Sunshine: A high performance self-routing broadband packet switch architecture,`` Proc. ISS, Stockholm, Sweden, pp. 123-129, May 1990, and in U.S. Pat. No. 4,893,304 (Giacopelli, et al ), overcomes some of the difficulties of the Starlite switch through a combination of output queuing and packet recirculation. The trap network operation in the Starlite system is modified in the Sunshine system so that up to K packets can be transferred to each output buffer through K parallel banyan routing networks. The trap network recirculates those packets that cannot be transferred to the output buffers.
An object of an aspect of this invention is to realize an exact implementation of an output-buffered packet switch that overcomes the complexity problems associated with implementations that use multiple disjoint paths through the use of multiple but shared interconnection paths, and that provides both shared and dedicated buffering, thus achieving buffer efficiency while avoiding the lockout problem.